#include <iostream>
using std::cout;
using std::endl;

// 数组存储大顶堆(完全二叉树)，再排序
/*
    80
  50   30
20
arr{80,50,30,20}
idx{ 0, 1, 2, 3}
size=4, 2个叶子节点

    80
  50   30
20 25
arr{80,50,30,20,25}
idx{ 0, 1, 2, 3, 4}
size=5, 3个叶子节点
*/
class Heap {
 public:
  Heap(int arr[], int size) : arr_(arr), size_(size) { Print(); }

  void Print() {
    for (int i = 0; i < size_; ++i) {
      cout << arr_[i] << ' ';
    }
    cout << endl;
  }

  // 一、建堆，时间复杂度O(n)。非叶子节点向下堆化
  void BuildHeap() {
    for (int i = size_ / 2 - 1; i >= 0; --i) {
      HeapifyToDown(i, size_);
    }
    Print();
  }

  // 二、排序，时间复杂度O(nlogn)
  void Sort() {
    for (int i = size_ - 1; i > 0; --i) {
      std::swap(arr_[0], arr_[i]);
      HeapifyToDown(0, i);
    }
    Print();
  }

  // 堆排序=建队+排序，总体时间复杂度O(nlogn)

 private:
  // 获取父子节点位置
  int ParentIdx(int idx) const { return (idx - 1) / 2; }
  int LeftChildIdx(int idx) const { return idx * 2 + 1; }
  int RightChildIdx(int idx) const { return idx * 2 + 2; }
  // 判断是否根节点
  bool IsRoot(int idx) const { return idx <= 0; }
  // 判断是否在子范围内
  bool InRange(int idx, int count) const { return idx < count; }
  // 往上堆化，时间复杂度O(n)
  void HeapifyToUp(int idx) {
    while (!IsRoot(idx)) {
      int parent = ParentIdx(idx);
      if (arr_[parent] < arr_[idx]) {
        std::swap(arr_[parent], arr_[idx]);
        idx = parent;
      } else {
        break;
      }
    }
  }
  // 往下堆化
  void HeapifyToDown(int idx, int count) {
    while (InRange(idx, count)) {
      int child = idx;
      int left = LeftChildIdx(idx);
      if (InRange(left, count)) {
        if (arr_[left] > arr_[idx]) {
          child = left;
        }
      }
      int right = RightChildIdx(idx);
      if (InRange(right, count)) {
        if (arr_[right] > arr_[idx] && arr_[right] > arr_[left]) {
          child = right;
        }
      }

      if (child == idx) break;
      std::swap(arr_[child], arr_[idx]);
      idx = child;
    }
  }

  int* arr_;
  int size_;
};

void TestHeap() {
  int arr[] = {4, 9, 8, 5, 3, 2, 10, 7};
  Heap heap(arr, sizeof(arr) / sizeof(int));
  /*
        4
      9    8
    5  3  2 10
  7
  */

  heap.BuildHeap();
  /*
        10
      9    8
    7  3  2  4
  5
  */

  heap.Sort();
  /*
        2
      3   4
    5  7 8  9
  10
  */
}

int main() { TestHeap(); }